폴라 코드 (Polar Codes)
1. 개요
폴라 코드(Polar Codes)는 2008년 에리크 릴리모이(Erdal Arikan) 교수에 의해 제안된 오류 정정 부호(Error Correction Code)로, 채널 분극화(Channel Polarization) 현상을 이용하여 데이터 전송 시 발생하는 오류를 복구하는 기술이다. 폴라 코드는 통신 이론의 기초가 되는 섀넌의 채널 용량(Shannon's Channel Capacity) 한계에 도달할 수 있음을 수학적으로 증명한 최초의 코드라는 점에서 학술적·기술적 의의가 매우 크다.
2. 동작 원리: 채널 분극화 (Channel Polarization)
폴라 코드의 핵심은 동일한 특성을 가진 여러 개의 독립적인 채널을 결합하여, 일부는 매우 신뢰할 수 있는 '깨끗한 채널'로, 나머지는 매우 신뢰할 수 없는 '잡음 섞인 채널'로 극단적으로 분리하는 채널 분극화(Channel Polarization) 메커니즘에 있다.
2.1 분극화 메커니즘
두 개의 동일한 이진 대칭 채널(Binary Symmetric Channel, BSC) $W$가 있을 때, 이를 결합하여 두 개의 가상 채널 $W^-$와 $W^+$를 생성한다.
- $W^-$ (나쁜 채널): 두 입력의 XOR 연산 결과가 전달되는 채널이다. 수신 측에서 $u_1$을 알지 못하는 상태에서 $u_2$를 결정해야 하므로, 잡음의 영향이 더 커진다.
- $W^+$ (좋은 채널): 이전 단계에서 결정된 $u_1$의 정보를 이용하여 잡음을 상쇄함으로써 신뢰도가 향상된 채널이다.
수학적으로, 채널의 신뢰도를 나타내는 용량(Capacity) $I(W)$에 대해 분극화 과정은 다음과 같은 경향을 보인다.
$$ \le I(W) \le I(W^+)$$
이 과정을 재귀적으로 반복하면, 채널의 신뢰도는 양극단으로 갈라지며, 코드 길이 $N = 2^n$이 증가할수록 분극화 현상은 더욱 뚜렷해진다.
2.2 채널 변환 구조
인코딩 과정에서는 다음과 같은 행렬 연산이 수행된다.
$$x = G_N u$$
여기서 $u$는 입력 벡터, $x$는 전송 벡터이며, 생성 행렬 $G_N$은 다음과 같이 재귀적으로 정의된다.
- 기본 행렬 ($N=2$): $G_2 = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$
- 재귀적 정의: $G_N = G_2^{\otimes n} = G_2 \otimes G_2 \otimes \dots \otimes G_2$ (총 $n$번의 크로네커 곱 수행)
3. 동결 비트 (Frozen Bits)
폴라 코드의 효율적인 전송을 위해 도입된 개념이 동결 비트(Frozen Bits)이다.
분극화 결과, 생성된 가상 채널들 중 신뢰도가 매우 낮은 채널에는 실제 정보(Information bits)를 싣지 않고, 송신자와 수신자가 미리 약속한 고정된 값(일반적으로 '0')을 채워 넣는다. 이를 '동결시킨다'고 표현한다.
- 정보 비트 (Information Bits): 신뢰도가 높은 채널에 배치되어 실제 데이터를 전송한다.
- 동결 비트 (Frozen Bits): 신뢰도가 낮은 채널에 배치되어 수신 측에서 해당 위치의 값을 이미 알고 있게 함으로써, 다른 정보 비트를 복구하는 힌트로 활용한다.
4. 인코딩 및 디코딩 과정
4.1 인코딩 (Encoding)
인코딩은 입력 벡터 $u$에 생성 행렬 $G_N$을 곱하는 단순한 선형 변환 과정이다. 정보 비트는 신뢰도 순서에 따라 선택된 인덱스에 배치되고, 나머지는 동결 비트로 채워진다.
4.2 디코딩 (Decoding)
폴라 코드는 기본적으로 순차적 제거(Successive Cancellation) 방식을 사용한다.
4.2.1 SC (Successive Cancellation) 디코딩
비트를 하나씩 순차적으로 결정하는 결정론적(Deterministic) 방식이다. 비트 $u_i$를 결정할 때, 이전에 결정된 비트들($u_1, \dots, u_{i-1}$)의 값을 기반으로 추론을 수행한다.
[SC 디코딩의 트리 구조 개념도]
[Root: 전체 수신 신호 y]
/ \
[Left] [Right] <-- 채널 분할 (분극화의 역과정)
/ \ / \
[u1] [u2] [u3] [u4] <-- 순차적 결정 (u1 -> u2 -> u3 -> u4)
^ ^ ^ ^
|______|______|______| (이전 결정값이 다음 결정의 조건으로 입력됨)
-
특징: 구현이 단순하고 복잡도가 낮으나, 한 번 오류가 발생하면 이후의 모든 비트 결정에 영향을 주는 '
오류 전파(Error Propagation)' 문제가 발생한다.
4.2.2 SCL (Successive Cancellation List) 디코딩
SC의 단점을 보완하기 위해, 하나의 경로가 아닌 $L$개의 유망한 경로(Candidate paths)를 동시에 추적하는 방식이다. 최종적으로 CRC(Cyclic Redundancy Check)를 통해 가장 가능성이 높은 경로를 선택한다.
- 특징: SC보다 훨씬 높은 오류 정정 성능을 보이며, 특히 짧은 코드 길이에서 매우 강력하다.
4.3 디코딩 알고리즘 비교
| 비교 항목 |
SC (Successive Cancellation) |
SCL (Successive Cancellation List) |
| 작동 방식 |
단일 경로 추론 |
$L$개의 다중 경로 추론 |
| 복잡도 |
낮음 ($O(N \log N)$) |
높음 ($O(L \cdot N \log N)$) |
| 오류 정정 능력 |
보통 (오류 전파 취약) |
매우 높음 (CRC 결합 시 최적) |
| 지연 시간 |
상대적으로 짧음 |
경로 관리로 인해 증가 |
5. 주요 특징 및 성능 분석
5.1 성능 특성
폴라 코드는 코드 길이 $N$이 커질수록 섀넌 한계에 수렴하는 특성을 가진다. 특히 짧은 블록 길이에서도 LDPC나 터보 코드보다 우수한 성능을 보일 수 있어, 제어 신호와 같은 소량의 데이터를 전송하는 데 최적화되어 있다.
5.2 기존 코드와의 비교
| 구분 |
폴라 코드 (Polar Codes) |
LDPC 코드 (Low-Density Parity-Check) |
터보 코드 (Turbo Codes) |
| 핵심 원리 |
채널 분극화 |
희소 패리티 검사 행렬 |
반복적 디코딩 (Iterative) |
| 최적성 |
섀넌 한계 도달 증명됨 |
근접함 |
근접함 |
| 복잡도 |
중간 (SCL 적용 시 증가) |
중간 (병렬 처리 최적화) |
높음 |
| 주요 용도 |
5G 제어 채널 (Control) |
5G 데이터 채널 (Data) |
4G LTE 데이터 채널 |
6. 실제 활용 및 표준화
6.1 5G NR (New Radio) 표준 채택
3GPP의 5G NR 표준에서는 데이터 전송 효율과 신뢰성을 모두 잡기 위해 용도에 따라 서로 다른 코드를 채택하였다. 폴라 코드는 특히 제어 채널(Control Channel)의 표준으로 선정되어 다음과 같은 주요 채널에 적용되었다.
구체적인 적용 사례:
- PBCH (Physical Broadcast Channel): 단말이 네트워크에 처음 접속할 때 필요한 필수 시스템 정보를 전송하는 채널로, 매우 높은 신뢰성이 요구된다.
- PDCCH (Physical Downlink Control Channel): 기지국이 단말기에 전송하는 하향링크 제어 정보(DCI)를 보호하기 위해 사용된다.
- PUCCH (Physical Uplink Control Channel): 단말기가 기지국으로 보내는 상향링크 제어 정보(ACK/NACK, CSI 등)의 신뢰성을 높이는 데 사용된다.
6.2 채택 배경
제어 채널은 데이터 채널에 비해 전송하는 비트 수가 적다(Short block length). LDPC 코드는 긴 데이터 패킷에서는 효율적이지만, 짧은 패킷에서는 성능이 급격히 저하되는 특성이 있다. 반면 폴라 코드는 SCL 디코딩과 CRC를 결합했을 때 짧은 길이에서도 매우 낮은 오류율(BER)을 유지하므로 제어 채널에 가장 적합한 기술로 평가받았다.
# 폴라 코드 (Polar Codes)
## 1. 개요
**폴라 코드(Polar Codes)**는 2008년 에리크 릴리모이(Erdal Arikan) 교수에 의해 제안된 오류 정정 부호(Error Correction Code)로, 채널 분극화(Channel Polarization) 현상을 이용하여 데이터 전송 시 발생하는 오류를 복구하는 기술이다. 폴라 코드는 통신 이론의 기초가 되는 **섀넌의 채널 용량(Shannon's Channel Capacity)** 한계에 도달할 수 있음을 수학적으로 증명한 최초의 코드라는 점에서 학술적·기술적 의의가 매우 크다.
## 2. 동작 원리: 채널 분극화 (Channel Polarization)
폴라 코드의 핵심은 동일한 특성을 가진 여러 개의 독립적인 채널을 결합하여, 일부는 매우 신뢰할 수 있는 '깨끗한 채널'로, 나머지는 매우 신뢰할 수 없는 '잡음 섞인 채널'로 극단적으로 분리하는 **채널 분극화(Channel Polarization)** 메커니즘에 있다.
### 2.1 분극화 메커니즘
두 개의 동일한 이진 대칭 채널(Binary Symmetric Channel, BSC) $W$가 있을 때, 이를 결합하여 두 개의 가상 채널 $W^-$와 $W^+$를 생성한다.
- **$W^-$ (나쁜 채널):** 두 입력의 XOR 연산 결과가 전달되는 채널이다. 수신 측에서 $u_1$을 알지 못하는 상태에서 $u_2$를 결정해야 하므로, 잡음의 영향이 더 커진다.
- **$W^+$ (좋은 채널):** 이전 단계에서 결정된 $u_1$의 정보를 이용하여 잡음을 상쇄함으로써 신뢰도가 향상된 채널이다.
수학적으로, 채널의 신뢰도를 나타내는 용량(Capacity) $I(W)$에 대해 분극화 과정은 다음과 같은 경향을 보인다.
$$ \le I(W) \le I(W^+)$$
이 과정을 재귀적으로 반복하면, 채널의 신뢰도는 양극단으로 갈라지며, 코드 길이 $N = 2^n$이 증가할수록 분극화 현상은 더욱 뚜렷해진다.
### 2.2 채널 변환 구조
인코딩 과정에서는 다음과 같은 행렬 연산이 수행된다.
$$x = G_N u$$
여기서 $u$는 입력 벡터, $x$는 전송 벡터이며, 생성 행렬 $G_N$은 다음과 같이 재귀적으로 정의된다.
- 기본 행렬 ($N=2$): $G_2 = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$
- 재귀적 정의: $G_N = G_2^{\otimes n} = G_2 \otimes G_2 \otimes \dots \otimes G_2$ (총 $n$번의 크로네커 곱 수행)
## 3. 동결 비트 (Frozen Bits)
폴라 코드의 효율적인 전송을 위해 도입된 개념이 **동결 비트(Frozen Bits)**이다.
분극화 결과, 생성된 가상 채널들 중 신뢰도가 매우 낮은 채널에는 실제 정보(Information bits)를 싣지 않고, 송신자와 수신자가 미리 약속한 고정된 값(일반적으로 '0')을 채워 넣는다. 이를 '동결시킨다'고 표현한다.
- **정보 비트 (Information Bits):** 신뢰도가 높은 채널에 배치되어 실제 데이터를 전송한다.
- **동결 비트 (Frozen Bits):** 신뢰도가 낮은 채널에 배치되어 수신 측에서 해당 위치의 값을 이미 알고 있게 함으로써, 다른 정보 비트를 복구하는 힌트로 활용한다.
## 4. 인코딩 및 디코딩 과정
### 4.1 인코딩 (Encoding)
인코딩은 입력 벡터 $u$에 생성 행렬 $G_N$을 곱하는 단순한 선형 변환 과정이다. 정보 비트는 신뢰도 순서에 따라 선택된 인덱스에 배치되고, 나머지는 동결 비트로 채워진다.
### 4.2 디코딩 (Decoding)
폴라 코드는 기본적으로 **순차적 제거(Successive Cancellation)** 방식을 사용한다.
#### 4.2.1 SC (Successive Cancellation) 디코딩
비트를 하나씩 순차적으로 결정하는 결정론적(Deterministic) 방식이다. 비트 $u_i$를 결정할 때, 이전에 결정된 비트들($u_1, \dots, u_{i-1}$)의 값을 기반으로 추론을 수행한다.
**[SC 디코딩의 트리 구조 개념도]**
```text
[Root: 전체 수신 신호 y]
/ \
[Left] [Right] <-- 채널 분할 (분극화의 역과정)
/ \ / \
[u1] [u2] [u3] [u4] <-- 순차적 결정 (u1 -> u2 -> u3 -> u4)
^ ^ ^ ^
|______|______|______| (이전 결정값이 다음 결정의 조건으로 입력됨)
```
- **특징:** 구현이 단순하고 복잡도가 낮으나, 한 번 오류가 발생하면 이후의 모든 비트 결정에 영향을 주는 '오류 전파(Error Propagation)' 문제가 발생한다.
#### 4.2.2 SCL (Successive Cancellation List) 디코딩
SC의 단점을 보완하기 위해, 하나의 경로가 아닌 $L$개의 유망한 경로(Candidate paths)를 동시에 추적하는 방식이다. 최종적으로 CRC(Cyclic Redundancy Check)를 통해 가장 가능성이 높은 경로를 선택한다.
- **특징:** SC보다 훨씬 높은 오류 정정 성능을 보이며, 특히 짧은 코드 길이에서 매우 강력하다.
### 4.3 디코딩 알고리즘 비교
| 비교 항목 | SC (Successive Cancellation) | SCL (Successive Cancellation List) |
| :--- | :--- | :--- |
| **작동 방식** | 단일 경로 추론 | $L$개의 다중 경로 추론 |
| **복잡도** | 낮음 ($O(N \log N)$) | 높음 ($O(L \cdot N \log N)$) |
| **오류 정정 능력** | 보통 (오류 전파 취약) | 매우 높음 (CRC 결합 시 최적) |
| **지연 시간** | 상대적으로 짧음 | 경로 관리로 인해 증가 |
## 5. 주요 특징 및 성능 분석
### 5.1 성능 특성
폴라 코드는 코드 길이 $N$이 커질수록 섀넌 한계에 수렴하는 특성을 가진다. 특히 짧은 블록 길이에서도 LDPC나 터보 코드보다 우수한 성능을 보일 수 있어, 제어 신호와 같은 소량의 데이터를 전송하는 데 최적화되어 있다.
### 5.2 기존 코드와의 비교
| 구분 | 폴라 코드 (Polar Codes) | LDPC 코드 (Low-Density Parity-Check) | 터보 코드 (Turbo Codes) |
| :--- | :--- | :--- | :--- |
| **핵심 원리** | 채널 분극화 | 희소 패리티 검사 행렬 | 반복적 디코딩 (Iterative) |
| **최적성** | 섀넌 한계 도달 증명됨 | 근접함 | 근접함 |
| **복잡도** | 중간 (SCL 적용 시 증가) | 중간 (병렬 처리 최적화) | 높음 |
| **주요 용도** | 5G 제어 채널 (Control) | 5G 데이터 채널 (Data) | 4G LTE 데이터 채널 |
## 6. 실제 활용 및 표준화
### 6.1 5G NR (New Radio) 표준 채택
3GPP의 5G NR 표준에서는 데이터 전송 효율과 신뢰성을 모두 잡기 위해 용도에 따라 서로 다른 코드를 채택하였다. 폴라 코드는 특히 **제어 채널(Control Channel)**의 표준으로 선정되어 다음과 같은 주요 채널에 적용되었다.
**구체적인 적용 사례:**
- **PBCH (Physical Broadcast Channel):** 단말이 네트워크에 처음 접속할 때 필요한 필수 시스템 정보를 전송하는 채널로, 매우 높은 신뢰성이 요구된다.
- **PDCCH (Physical Downlink Control Channel):** 기지국이 단말기에 전송하는 하향링크 제어 정보(DCI)를 보호하기 위해 사용된다.
- **PUCCH (Physical Uplink Control Channel):** 단말기가 기지국으로 보내는 상향링크 제어 정보(ACK/NACK, CSI 등)의 신뢰성을 높이는 데 사용된다.
### 6.2 채택 배경
제어 채널은 데이터 채널에 비해 전송하는 비트 수가 적다(Short block length). LDPC 코드는 긴 데이터 패킷에서는 효율적이지만, 짧은 패킷에서는 성능이 급격히 저하되는 특성이 있다. 반면 폴라 코드는 SCL 디코딩과 CRC를 결합했을 때 짧은 길이에서도 매우 낮은 오류율(BER)을 유지하므로 제어 채널에 가장 적합한 기술로 평가받았다.